/*
 * @Author: szx
 * @Date: 2022-04-06 12:49:08
 * @LastEditTime: 2022-04-06 12:58:06
 * @Description:
 * @FilePath: \leetcode\剑指offerII\040\040.js
 */
var maximalRectangle = function (matrix) {
    if (matrix.length == 0 || matrix[0].length == 0) return 0;
    const n = matrix[0].length;
    const height = new Array(n).fill(0);
    let res = 0;
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] == '0') height[j] = 0;
            else height[j]++;
        }
        res = Math.max(res, largestRectangleArea(height));
    }
    return res;
};

var largestRectangleArea = function (heights) {
    // 从栈顶到栈底为单调递减的
    let res = 0;
    const st = [0];
    heights = [0, ...heights, 0]; // 数组头部加入元素0 数组尾部加入元素0
    for (let i = 1; i < heights.length; i++) {
        while (st.length && heights[i] < heights[st[st.length - 1]]) {
            const mid = st.pop();
            res = Math.max(res, (i - st[st.length - 1] - 1) * heights[mid]);
        }
        st.push(i);
    }
    return res;
};
